package lib

import (
	"algorithms/ds"
	"math"
	"strconv"
	"strings"
)

func init() {
	Probs = append(Probs, Problem{
		Num:         449,
		Discription: "二叉搜素树的序列化和反序列化",
		Level:       3,
		Labels: map[string]int{
			"二叉树":  1,
			"前序遍历": 1,
			"回溯":   1,
		},
	})
}

// 正常的二叉树需要中序遍历、前序遍历和后序遍历中的一个才能唯一确定
// 二叉搜索树可以根据前序遍历或者后序遍历中的一个确定
type Codecc struct {
}

func Constructor10() Codecc {
	return Codecc{}
}

// 按前序遍历记录
// Serializes a tree to a single string.
func (c *Codecc) Serialize(root *ds.TreeNode) string {
	if root == nil {
		return ""
	}

	var builder strings.Builder
	cur := root
	s := make([]*ds.TreeNode, 0)
	for cur != nil || len(s) > 0 {
		for cur != nil {
			builder.WriteString(",")
			builder.WriteString(strconv.Itoa(cur.Val))
			s = append(s, cur)
			cur = cur.Left
		}

		top := s[len(s)-1]
		s = s[:len(s)-1]
		cur = top.Right
	}

	res := builder.String()
	return res[1:]
}

// 按前序遍历的顺序构造
// 前序遍历数组的第一个为根节点的值，如果第二个值满足上下界的话，第二个值为左子树根节点的值，以此类推
// Deserializes your encoded data to tree.
func (c *Codecc) Deserialize(data string) *ds.TreeNode {
	if data == "" {
		return nil
	}

	rootIndex := 0
	vals := strings.Split(data, ",")
	var dfs func(int, int) *ds.TreeNode
	dfs = func(lower int, upper int) *ds.TreeNode {
		//有值的节点都构造完了，剩nil
		if rootIndex >= len(vals) {
			return nil
		}

		val, _ := strconv.Atoi(vals[rootIndex])
		//如果不满足上下界，说明不是对应子树上的节点，对应的孩子为nil
		if val < lower || val > upper {
			return nil
		}

		//取根节点的值，将根节点的索引移动到可能左子树上
		rootIndex++
		node := &ds.TreeNode{
			Val: val,
		}
		//更新上下界，按照前序遍历顺序构造
		node.Left = dfs(lower, val)
		node.Right = dfs(val, upper)
		return node
	}

	return dfs(math.MinInt32, math.MaxInt32)
}
